public class BinarySearchTree {

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;
        TreeNode(int key) {
            this.key = key;
        }
    }

    public TreeNode root;

    /**
     * 插入一个元素
     *
     * @param key
     */
    public boolean insert(int key) {
        TreeNode ret=new TreeNode(key);
        //判断此树是不是空树
        if(root==null){
            root=ret;
            return true;
        }
        TreeNode parent=null;
        TreeNode cur=root;
        while(cur!=null){
            //判断它是不是大于此节点的值
            if(cur.key<key) {//大于根节点，往右边插
                parent=cur;//记录父亲节点
                cur=cur.right;
            }else if(cur.key>key) {//小于根节点的，往左边插
                parent =cur;
                cur=cur.left;
            }
        }//此时到了叶子节点
        if(ret.key< parent.key){
            parent.left=ret;
        }else {
            parent.right=ret;
        }
        return  true;
    }

    //查找key是否存在
    public TreeNode search(int key) {
      //查找根节点是否为null
        if(root==null){
            return null;
        }
        TreeNode cur=root;
        while(cur!=null){
            if(cur.key>key){//比根节点小
                cur=cur.left;
            }else if(cur.key<key){//比根节点大
                cur=cur.right;
            }else{
                return cur;//找到
            }
        }
        return null;
    }

    //删除key的值
    public boolean remove(int key) {
        //cur是待删除的节点。parent是待删除节点的父亲节点
        if (root == null) {//先判断此树是不是为空
            return false;
        }//不为空。分为三种情况
        //cur.left==null
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (cur.key < key) {
                parent = cur;
                cur = cur.right;
            } else if (cur.key > key) {
                parent = cur;
                cur = cur.left;
            } else {//此时找到
                //删除该节点
                removeChild(cur, parent);
            }
        }
        return true;
    }
    //删除节点
    public  void removeChild(TreeNode cur,TreeNode parent){
        //分三种情况
        //1 cur.left==null
        if(cur.left==null){
            //判断是不是根节点
            if(cur.equals(root)){
                root=root.right;
            }
            if(cur.equals(parent.left)){
                parent.left=cur.left;
            }
            if(cur.equals(parent.right)){
                parent.left=cur.right;
            }
        }else if(cur.right==null){ //2.cur.right==null
           if(cur.equals(root)){
               root=root.left;
           }
           if(cur.equals(parent.right)){
               parent.right=cur.left;
           }
           if(cur.equals(parent.left)){
               parent.left=cur.left;
           }
        }else{//3.cur.left!=null&&cur.right!=null
            //用一个叫做替罪羊
            //可以找左树的最右边，就是左边最大的，也小于根节点
            //可以找右边的最左边，就是右边最小的，也大于根节点
            TreeNode target=cur.left;//左树
            TreeNode targetParent=cur;
            while(target.right!=null){//左树的最右边
                targetParent=target;
                target=target.right;
            }
            cur.key=target.key;//将替罪羊的值赋值给cur
            //将替罪羊删除
            if(target.equals(targetParent.left)){
                targetParent.left=target.left;
            }else{
                targetParent.right=target.right;
            }
        }
    }
}
 
   